前言

昨天說到強化學習中 TD Learning 方法下，有分為 on-policy 與 off-policy 演算法。在說明 on-policy 與 off-policy 的差別後，我們入兩個演算法的名稱 ─ SARSA 與 Q-Learning，今天我們要先實作 SARSA。

另外昨天的文章有做修正，是關於 SARSA 是 step-update 還是 episode-update 的問題。昨天提到 1994 年 Rummery 與 Niranjan 提出的 SARSA 原型是 episode-update，但在他們的原文中，我並沒有看相關的討論。之後會再去看 Wilson 的原文，不過因為不確定的關係，所以先做修正。

實作 SARSA

今天要實作的 SARSA，這邊分為五個函數處理，分別為

• 模擬環境中運行 (SimProc)
• 決定動作 (GetAction)
• 更新價值函數 (ValueUpdate)
• 顯示目前最佳策略 (PrintGreedyPolicy)
• 主程式 (main)

其中 GetAction 用來方便執行 - greedy；PrintGreedyPolicy 用於呈現各狀態的最佳動作。因為沒有太多特殊內容，因此下方不特別貼出來說明。若有執行的需求，可以到 GitHub 獲得完整程式碼。

SimProc

負責處理在單一 episode 中遇到的所有事情，包含取得狀態、決定動作、取得回饋、更新價值、判斷是否結束...等過程，程式碼如下：

def SimProc(action_value, reward, trans_mat, steps, gamma, alpha, epsilon):
    # initialize setting
    record = []
    state = np.random.randint(1,15)
    action = GetAction(action_value, epsilon, state)
    for step in range(steps):
        # get next infromation
        next_state = np.argmax(trans_mat[:,state,action])
        next_action = GetAction(action_value, epsilon, next_state)
        record.append([state, action, reward[next_state], next_state, next_action])
        # update action value
        action_value[state, action] = ValueUpdate(action_value, record[step], alpha, gamma)
        # update for next step
        state = next_state
        action = next_action
        if state == 0 or state == 15:
            break
    return action_value

這裡需要特別注意的是，在 record 中有紀錄 next_action，並用於更新動作價值。

註 1 ：可以明天與 Q-Learning 比較
註 2 ：SARSA 是 State-Action-Reward-State-Action 的開頭縮寫，表示該演算法使用這些參數更新。

ValueUpdate

負責處理動作價值的更新，是 SARSA 與 Q-Learning 區別的核心部分，程式碼如下：

def ValueUpdate(action_value, record, alpha, gamma):
    state = record[0]
    action = record[1]
    reward = record[2]
    next_state = record[3]
    next_action = record[4]
    now_value = action_value[state, action]
    update_value = alpha*(reward + gamma*action_value[next_state, next_action] - now_value)
    value = now_value + update_value
    return value

請特別注意變數 update_value，這邊我們使用「下一步狀態」和「下一步動作」的動作價值，更新動作價值。

註 1 ：可以明天與 Q-Learning 比較

main

這個設定 GridWorld 環境參數、演算法參數、移動次數，詳細內容如下：

def main(Episodes):
    # Environment setting
    ActionValue = np.zeros([16,4])
    Reward = np.full(16, -1)
    Reward[0] = 0
    Reward[-1] = 0
    TransMat = np.load('./gridworld/T.npy')
    # parameters setting
    Gamma = 0.99
    Steps = 50
    Alpha = 0.05

    # Execute
    for episode in range(Episodes):
        Epsilon = 1/(episode+1)
        ActionValue = SimProc(ActionValue, Reward, TransMat, Steps, Gamma, Alpha, Epsilon)
        PrintGreedyPolicy(episode, ActionValue)
        #time.sleep(1)

關於環境的設定與之前沒有差異，演算法的部分有兩點要注意

• 新增一個演算法 alpha，用來決定每次動作價值要更新多少
• epsilon 改用 1/(episode+1)，一樣會浮動，但浮動的狀態比之前的設定更劇烈 (參考書上設定)。

註 1 ：Python 的數列起始於 0，因此在計算時寫成 (episode+1)
註 2 ：如果想要有迭代更新的感覺，一樣可以把最後一行 '#time.sleep(1)' 前面的 '#' 去除

執行結果

以下為執行 1000 episodes 的策略結果

============================================================
[Greedy Policy]
Episode: 1000
[['*' '<' '<' 'v']
 ['^' '^' '>' 'v']
 ['^' '<' '>' 'v']
 ['^' '>' '>' '*']]
============================================================

算是一個很完美的結果，明天 Q-Learning 表現會如何呢？